package com.such.kit.datastructure.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
import com.such.kit.Logger;
import com.such.kit.MathCalculate;
import com.such.kit.datastructure.graph.bean.Edge;
import com.such.kit.datastructure.graph.bean.Vertex;
import com.such.kit.datastructure.graph.exception.LoopException;
import com.such.kit.datastructure.graph.support.Graph;
import com.such.kit.string.StringCommons;
import com.such.kit.validate.ValidateCommons;
import com.such.kit.validate.ValidateNumber;

/**
 * @作者 SUCH
 * @日期 2016-9-27 下午3:32:49
 * @描述 有向图实现（顶点到顶点有明确指向，既从 A 顶点到 B 顶点）
 * @param <T>
 */
public class DirectedGraph<T> implements Graph<T>, java.io.Serializable {

	private static final long serialVersionUID = 4057495887612434712L;

	/**
	 * vertices：顶点集
	 * 需要按照插入顺序保存顶点，这将影响图的遍历算法正确性
	 */
	private Map<T, Vertex<T>> vertices = new LinkedHashMap<T, Vertex<T>>();
	/** edgeCount：记录边的总数 */
	private int edgeCount;

	public Vertex<T> getVertex(T label) {
		return this.vertices.get(label);
	}

	public Vertex<T> addVertex(T label) {
		Vertex<T> vertex = getVertex(label);
		if (ValidateCommons.isEmpty(vertex)) {
			vertex = new Vertex<T>(label);
			this.vertices.put(label, vertex);
		}
		return vertex;
	}

	public Vertex<T> removeVertex(T label) {
		Vertex<T> vertex = this.vertices.get(label);
		if (ValidateCommons.isNotEmpty(vertex)) {
			for (Edge<T> edge : vertex.getInEdges()) {
				// 获取所有入度边顶点
				Vertex<T> targetVertex = edge.getTargetVertex();
				// 从入度边顶点删除与当前顶点的出度边
				targetVertex.disconnectNeighbor(vertex);
			}
			for (Edge<T> edge : vertex.getOutEdges()) {
				// 获取所有出度边顶点
				Vertex<T> targetVertex = edge.getTargetVertex();
				// 从出度边顶点删除与当前顶点的入度边
				targetVertex.disconnectMe(vertex);
			}
			this.vertices.remove(vertex);
		}
		return vertex;
	}

	public boolean addEdge(T begin, T end) {
		return addEdge(begin, end, 1, false);
	}

	public boolean addEdge(T begin, T end, double weight, boolean checkLoop) {
		boolean isNewBeginVertex = false;
		Vertex<T> beginVertex = getVertex(begin);
		if (ValidateCommons.isEmpty(beginVertex)) {
			// 当未获取到顶点则标记为新顶点
			isNewBeginVertex = true;
			beginVertex = addVertex(begin);
		}
		boolean isNewEndVertex = false;
		Vertex<T> endVertex = getVertex(end);
		if (ValidateCommons.isEmpty(endVertex)) {
			// 当未获取到顶点则标记为新顶点
			isNewEndVertex = true;
			endVertex = addVertex(end);
		}

		// 添加出度边
		boolean result = beginVertex.connectNeighbor(endVertex, weight);
		if (result) {
			// 添加入度边
			endVertex.connectMe(beginVertex, weight);
			this.edgeCount++;
		}

		if (checkLoop && checkLoop()) {
			String message = StringCommons.merger(begin.toString(), " 连接 ", end.toString(), " 使图形成了环");
			Logger.warn(getClass(), message);

			// 执行回滚开始
			// 删除边
			removeEdge(begin, end);
			if (isNewBeginVertex) {
				// 如果为新顶点则删除顶点
				this.vertices.remove(begin);
			}
			if (isNewEndVertex) {
				// 如果为新顶点则删除顶点
				this.vertices.remove(end);
			}
			this.edgeCount--;
			result = false;
			// 执行回滚结束
		}
		return result;
	}

	public void removeEdge(T begin, T end) {
		// 边的开始顶点
		Vertex<T> beginVertex = getVertex(begin);
		// 边的结束顶点
		Vertex<T> endVertex = getVertex(end);
		if (ValidateCommons.isNotEmpty(beginVertex)) {
			// 从 beginVertex 删除与 endVertex 的出度边
			beginVertex.disconnectNeighbor(endVertex);
		}
		if (ValidateCommons.isNotEmpty(endVertex)) {
			// 从 endVertex 删除与 beginVertex 的入度边
			endVertex.disconnectMe(beginVertex);
		}
	}

	public boolean hasEdge(T begin, T end) {
		// 边的开始顶点
		Vertex<T> beginVertex = getVertex(begin);
		// 边的结束顶点
		Vertex<T> endVertex = getVertex(end);
		if (ValidateCommons.isEmpty(beginVertex) || !beginVertex.hasNeighbor() || ValidateCommons.isEmpty(endVertex)) {
			return false;
		}
		// 遍历出度边
		for (Edge<T> edge : beginVertex.getOutEdges()) {
			Vertex<T> targetVertex = edge.getTargetVertex();
			// 比较出度边顶点与 endVertex，相等则边存在
			if (targetVertex.equals(endVertex)) {
				return true;
			}
		}
		return false;
	}

	public int getVertexSize() {
		return this.vertices.size();
	}

	public int getEdgeSize() {
		return this.edgeCount;
	}

	public boolean isEmpty() {
		return this.vertices.isEmpty();
	}

	public void clear() {
		this.vertices.clear();
		this.edgeCount = 0;
	}

	public List<T> getDepthFirstTraversal(T origin) {
		// 初始化顶点
		resetVertices();
		// 起始顶点
		Vertex<T> originVertex = getVertex(origin);
		originVertex.setVisited(true);
		// 保存遍历顺序
		List<T> traversalOrder = new LinkedList<T>();
		traversalOrder.add(originVertex.getLabel());
		
		// 遍历辅助栈
		Stack<Vertex<T>> vertexStack = new Stack<Vertex<T>>();
		// 将基准顶点入栈
		vertexStack.push(originVertex);
		while (!vertexStack.isEmpty()) {
			// 取栈的顶部顶点（最后入栈的顶点）
			Vertex<T> topVertex = vertexStack.peek();
			Vertex<T> nextNeighbor = topVertex.getNextUnvisitedNeighbor();
			if (ValidateCommons.isNotEmpty(nextNeighbor)) {
				traversalOrder.add(nextNeighbor.getLabel());
				// 将邻接点入栈，此时 nextNeighbor 则成为栈新的顶部顶点，因此下次 while 会处理此顶点
				vertexStack.push(nextNeighbor);
			} else {
				// 当未找到未访问的邻接点，则此条深度遍历结束，执行出栈，因此下次 while 会处理其前置顶点
				vertexStack.pop();
			}
		}
		return traversalOrder;
	}

	public List<T> getBreadthFirstTraversal(T origin) {
		// 初始化顶点
		resetVertices();
		// 起始顶点
		Vertex<T> originVertex = getVertex(origin);
		originVertex.setVisited(true);
		// 保存遍历顺序
		List<T> traversalOrder = new LinkedList<T>();
		traversalOrder.add(originVertex.getLabel());

		// 遍历辅助队列
		Queue<Vertex<T>> vertexQueue = new LinkedList<Vertex<T>>();
		// 将基准顶点入队列
		vertexQueue.offer(originVertex);
		while (!vertexQueue.isEmpty()) {
			// 移除并返回队列的第一个顶点（最先入队列的顶点）
			Vertex<T> frontVertex = vertexQueue.poll();
			if (ValidateCommons.isNotEmpty(frontVertex)) {
				// 遍历所有邻接点
				for (Edge<T> edge : frontVertex.getOutEdges()) {
					Vertex<T> targetVertex = edge.getTargetVertex();
					if (!targetVertex.isVisited()) {
						targetVertex.setVisited(true);
						traversalOrder.add(targetVertex.getLabel());
						// 将邻接点入队列，此时 targetVertex 则成为队列新的第一个顶点，因此下次 while 会处理此顶点
						vertexQueue.offer(targetVertex);
					}
				}
			}
		}
		return traversalOrder;
	}

	public List<T> getShortestPath(T begin, T end) {
		/*
		 * 查找最短路径其实可以看作是对广度优先遍历的应用
		 * 广度优先遍历会按照层级，一层一层往下遍历
		 * 在遍历过程中遇到第一个顶点邻接点与 endVertex 相等，则可认为到此顶点是最短路径（遍历的层数最少）
		 * 即使在同一层有其它顶点的的邻接点与 endVertex 相等，无非就是有 2 条最短路径
		 */

		// 初始化顶点
		resetVertices();
		// 开始顶点
		Vertex<T> beginVertex = getVertex(begin);
		beginVertex.setVisited(true);
		// 结束顶点
		Vertex<T> endVertex = getVertex(end);

		// 遍历辅助队列
		Queue<Vertex<T>> vertexQueue = new LinkedList<Vertex<T>>();
		// 将开始顶点入队列
		vertexQueue.offer(beginVertex);
		while(!vertexQueue.isEmpty()) {
			// 移除并返回队列的第一个顶点（最先入队列的顶点）
			Vertex<T> frontVertex = vertexQueue.poll();
			if (ValidateCommons.isNotEmpty(frontVertex)) {
				// 遍历所有邻接点
				for (Edge<T> edge : frontVertex.getOutEdges()) {
					Vertex<T> targetVertex = edge.getTargetVertex();
					if (!targetVertex.isVisited()) {
						targetVertex.setVisited(true);
						// 将遍历过程中的前置顶点保存下来，既记录了路径路线
						targetVertex.setPredecessorVertex(frontVertex);
						// 将邻接点入队列，此时 targetVertex 则成为队列新的第一个顶点，因此下次 while 会处理此顶点
						vertexQueue.offer(targetVertex);
					}
					if (targetVertex.equals(endVertex)) {
						// 当遇到 targetVertex 与 endVertex 相等，则找到了最近路径
						// 将 vertexQueue 清空，结束 while
						vertexQueue.clear();
					}
				}
			}
		}

		List<T> paths = new ArrayList<T>();
		Vertex<T> vertex = endVertex;
		while (ValidateCommons.isNotEmpty(vertex)) {
			paths.add(0, vertex.getLabel());
			vertex = vertex.getPredecessorVertex();
		}
		return paths;
	}

	public int getShortestPathLength(T begin, T end) {
		return getShortestPath(begin, end).size();
	}

	public List<T> getCheapestPath(T begin, T end) {
		getCheapestPathByDijkstra(begin);
		List<T> paths = new ArrayList<T>();
		Vertex<T> endVertex = getVertex(end);
		paths.add(endVertex.getLabel());
		Vertex<T> vertex = endVertex.getPredecessorVertex();
		if (ValidateCommons.isEmpty(vertex)) {
			String message = StringCommons.merger(begin.toString(), " 到 ", end.toString(), " 无畅通路径");
			Logger.warn(getClass(), message);
			throw new RuntimeException(message);
		}
		while (ValidateCommons.isNotEmpty(vertex)) {
			paths.add(0, vertex.getLabel());
			vertex = vertex.getPredecessorVertex();
		}
		return paths;
	}

	public double getCheapestPathCost(T begin, T end) {
		Map<Vertex<T>, Double> costMapping = getCheapestPathByDijkstra(begin);
		Double minCost = costMapping.get(getVertex(end));
		if (ValidateCommons.isEmpty(minCost)) {
			String message = StringCommons.merger(begin.toString(), " 到 ", end.toString(), " 无畅通路径");
			Logger.warn(getClass(), message);
			throw new RuntimeException(message);
		}
		return minCost;
	}

	private Map<Vertex<T>, Double> getCheapestPathByDijkstra(T begin) {
		/*
		 * 基于 Dijkstra 算法的最低费实现，因此不支持边的分值为负数
		 */

		// 初始化顶点
		resetVertices();
		// 开始顶点
		Vertex<T> beginVertex = getVertex(begin);

		// 保存 beginVertex 到每个顶点的最低费用
		Map<Vertex<T>, Double> costMapping = new HashMap<Vertex<T>, Double>();
		// 保存  beginVertex，到原点费用为 0
		costMapping.put(beginVertex, 0D);

		// 遍历辅助队列
		Queue<Vertex<T>> vertexQueue = new LinkedList<Vertex<T>>();
		// 将开始顶点入队列
		vertexQueue.offer(beginVertex);
		while(!vertexQueue.isEmpty()) {
			// 移除并返回队列的第一个顶点（最先入队列的顶点）
			Vertex<T> frontVertex = vertexQueue.poll();
			if (ValidateCommons.isNotEmpty(frontVertex)) {
				// 取前置顶点费用
				double predecessorCost = costMapping.get(frontVertex);
				// 遍历所有邻接点
				for (Edge<T> edge : frontVertex.getOutEdges()) {
					Vertex<T> targetVertex = edge.getTargetVertex();
					double cost = MathCalculate.add(predecessorCost, edge.getWeight()).doubleValue();
					Double checkCost = costMapping.get(targetVertex);
					if (ValidateCommons.isEmpty(checkCost)) {
						// checkCost 为空说明 targetVertex 第一次入队列
						vertexQueue.offer(targetVertex);

						// 保存 targetVertex 的费用及其前置顶点
						costMapping.put(targetVertex, cost);
						targetVertex.setPredecessorVertex(frontVertex);
					} else if (ValidateNumber.lt(cost, checkCost)) {
						// 当 [frontVertex 费用 + targetVertex 费用 < targetVertex 在 costMapping 中保存的费用]
						// 说明有到 targetVertex 费用更低的路径
						// 更新 targetVertex 的费用及其前置顶点
						costMapping.put(targetVertex, cost);
						targetVertex.setPredecessorVertex(frontVertex);
					}
				}
			}
		}
		return costMapping;
	}

	public List<T> getTopologicalSort() {
		// 初始化顶点
		resetVertices();
		// 保存拓扑顺序
		List<T> topologicalOrder = new LinkedList<T>();

		// 获取入度为 0 的顶点
		List<Vertex<T>> inDegreeZeroVertices = getInDegreeZeroVertices();
		while (ValidateCommons.isNotEmpty(inDegreeZeroVertices)) {
			for (Vertex<T> vertex : inDegreeZeroVertices) {
				// 当入度为 0，则设置为已访问
				vertex.setVisited(true);
				// 入度减 1（-1）
				vertex.setInEdgeCount(vertex.getInEdgeCount() - 1);
				// 遍历所有邻接点
				for (Edge<T> edge : vertex.getOutEdges()) {
					Vertex<T> targetVertex = edge.getTargetVertex();
					// 入度减 1
					targetVertex.setInEdgeCount(targetVertex.getInEdgeCount() - 1);
				}

				topologicalOrder.add(vertex.getLabel());
			}
			// 获取下一批入度为 0 的顶点
			inDegreeZeroVertices = getInDegreeZeroVertices();
		}

		// 检查是否存在未访问的顶点
		List<Vertex<T>> unvisitedVertices = getUnvisitedVertices();
		if (ValidateCommons.isNotEmpty(unvisitedVertices)) {
			// 如果有则图中有顶点形成了环，抛出异常
			throw new LoopException(unvisitedVertices);
		}

		return topologicalOrder;
	}

	public boolean checkLoop() {
		try {
			getTopologicalSort();
		} catch (LoopException e) {
			Logger.warn(getClass(), e.getMessage());
			return true;
		}
		return false;
	}

	public Vertex<T> getNextUnvisitedVertex() {
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			if (!vertex.isVisited()) {
				vertex.setVisited(true);
				return vertex;
			}
		}
		return null;
	}

	public List<Vertex<T>> getUnvisitedVertices() {
		List<Vertex<T>> unvisitedVertices = new ArrayList<Vertex<T>>();
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			if (!vertex.isVisited()) {
				vertex.setVisited(true);
				unvisitedVertices.add(vertex);
			}
		}
		return unvisitedVertices;
	}

	public Vertex<T> getNextInDegreeZeroVertex() {
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			if (vertex.getInEdgeCount() == 0) {
				return vertex;
			}
		}
		return null;
	}

	public List<Vertex<T>> getInDegreeZeroVertices() {
		List<Vertex<T>> inDegreeZeroVertices = new ArrayList<Vertex<T>>();
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			if (vertex.getInEdgeCount() == 0) {
				inDegreeZeroVertices.add(vertex);
			}
		}
		return inDegreeZeroVertices;
	}

	public Vertex<T> getNextOutDegreeZeroVertex() {
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			if (vertex.getOutEdgeCount() == 0) {
				return vertex;
			}
		}
		return null;
	}

	public List<Vertex<T>> getOutDegreeZeroVertices() {
		List<Vertex<T>> outDegreeZeroVertices = new ArrayList<Vertex<T>>();
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			if (vertex.getOutEdgeCount() == 0) {
				outDegreeZeroVertices.add(vertex);
			}
		}
		return outDegreeZeroVertices;
	}

	public void resetVertices() {
		Iterator<Vertex<T>> it = this.vertices.values().iterator();
		while (it.hasNext()) {
			Vertex<T> vertex = it.next();
			vertex.reset();
		}
	}

}
